package test03;


import java.util.*;

public class Partition {
    public ListNode partition(ListNode pHead, int val) {
        /*if(pHead == null) return null;
        Stack<Integer> stack = new Stack<>();

        ListNode cur = pHead;
        ListNode prev = null;
        while(cur!=null) {
            if(cur.val < val) {
                stack.add(cur.val);
                if(cur == pHead) {
                    pHead = pHead.next;
                    cur = pHead;
                }else {
                    cur = cur.next;
                    prev.next = cur;
                }
            }else {
                prev = cur;
                cur = cur.next;
            }
        }
        while(!stack.isEmpty()) {
            ListNode newNode = new ListNode(stack.pop());
            newNode.next = pHead;
            pHead = newNode;
        }
        return pHead;*/

        if(pHead == null) return null;
        ListNode cur = pHead;

        Stack<Integer> stack = new Stack<>();
        while (cur != null) {
            if(pHead.val < val) {
                stack.add(pHead.val);
                if(cur == pHead){
                    pHead = pHead.next;
                    cur = pHead;
                }else {
                    cur = cur.next;
                }
            }else {

                cur = cur.next;

            }
        }
        while(!stack.isEmpty()) {
            ListNode newnode = new ListNode(stack.pop());
            newnode.next = pHead;
            pHead = newnode;
        }
        return pHead;
    }
}